/* Copyright 2011 Tobias Marschall, Email: tm@cwi.nl 
 * 
 * This file is part of string-cover.
 *
 * string-cover is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * string-cover is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with string-cover.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef SUBSTRINGSTORE_H_
#define SUBSTRINGSTORE_H_

#include <vector>
#include <string>

/** Given a vector of strings, this class assigns a number to every contained (non-empty) substring.
 *  TODO: This implementation takes quadratic space, where it could be done in linear
 *        space. */
class SubstringStore {
private:
	const std::vector<std::string>* strings;
	typedef struct {
		size_t index;
		size_t start;
		size_t length;
	} interval_t;
	/** Vector containing representative intervals for every substring. */
	std::vector<interval_t> index_to_interval;
	/** List of number of occurrences of each substring. */
	std::vector<size_t> index_to_count;
	/** Three dimensional array giving the index for every interval, i.e.
	 *  interval_to_index[string_nr][start_pos][length-1] gives the index of the
	 *  respective interval. */
	size_t*** interval_to_index;
public:
	SubstringStore(const std::vector<std::string>* strings);
	virtual ~SubstringStore();

	/** Returns the index of the substring of strings[string_nr] that spans from
	 *  start_pos (inclusively) to end_pos (exclusively). */
	size_t getIndex(size_t string_nr, size_t start_pos, size_t end_pos) const;

	/** Returns the number of different substrings. */
	size_t size() const;

	/** Returns the substring the belongs to the given index. */
	std::string getSubstring(size_t index) const;

	/** Returns the number of occurrences of the substring belonging to the given index.*/
	size_t getCount(size_t index) const;
};

#endif /* SUBSTRINGSTORE_H_ */
